Sebaik sahaja Marius pulang, beliau membuat pakatan politiknya dengan mengahwini Julia dari keluarga Caesar: isterinya merupakan ibu saudara diktator yang akan datang iaitu Julius Caesar. Perkahwinan ini telah mula mengukuhkan pengaruhnya di arena politik Rom.

Kemudian beliau kembali dalam alam tentera sewaktu peperangan Jugurthine di bawah Caecilius Metellus, dimana beliau cuba untuk mengatasi komandernya ini. Marius juga telah mendapat sokongan padu tentera bawahannya sehinggakan ramai dari mereka yang percaya beliau patut dipilih sebagai konsul di Rom. Metellus semakin cemburu dengan populariti beliau dan menjadi dingin terhadap Marius. Marius sedar bahawa ketuanya bersama para bangsawan yang lain tidak mahu beliau dipilih sebagai Konsul. Lalu beliaupun berlayar balik ke Rom dan meminta untuk dicalonkan selepas 'menyerang' Metellus di Senat serta berjanji untuk membawa Jugurtha pulang sama ada hidup atau mati.

Oleh kerana kesungguhannya untuk menawan Jugurtha, pihak Populares telah memilihnya sebagai Konsul. Sewaktu itu beliau telah berkongsi kuasa dengan konsul Catulus. Marius tahu bahawa beliau bukan seorang bangsawan tetapi Rom amat bergantung dengan angkatan tenteranya yang kuat. Oleh itu, beliau telah melakukan beberapa reformasi dalam ketenteraan Rom. Langkahnya yang paling drastik ialah dengan membenarkan proletarii atau orang yang tidak berharta sebagai tentera. Tujuannya ialah untuk membuktikan bahawa orang yang miskin juga mampu untuk mencapai darjat yang tinggi. Disamping itu, beliau telah membidas golongan bangsawan dengan mengatakan bahawa adalah lebih baik untuk menjadi seorang yang mahir dari dilahirkan dalam golongan berada.

Selepas itu, Marius pulang Afrika dimana Metellus enggan berjumpanya kerana dia mendakwa Marius cuba mengugat posisinya sebagai ketua. Namun di Afrika kedua-dua Marius dan Metellus, gagal menawan Jugurtha. Tetapi orang yang berjaya melakukannya ialah anak didik serta quaestor Marius sendiri iaitu Lucius Cornelius Sulla. Ini telah mencetuskan persengketaan yang berpanjangan antara beliau dengan Sulla.